πŸ‘©β€πŸ’» 2668. 숫자 κ³ λ₯΄κΈ°

@Seongukbaek Posted January 13, 2022 Β· Updated January 13, 2022 Β· 5 min read

문제

μ„Έλ‘œ 두 쀄, κ°€λ‘œλ‘œ N개의 칸으둜 이루어진 ν‘œκ°€ μžˆλ‹€. 첫째 μ€„μ˜ 각 μΉΈμ—λŠ” μ •μˆ˜ 1, 2, …, N이 μ°¨λ‘€λŒ€λ‘œ λ“€μ–΄ 있고 λ‘˜μ§Έ μ€„μ˜ 각 μΉΈμ—λŠ” 1이상 Nμ΄ν•˜μΈ μ •μˆ˜κ°€ λ“€μ–΄ μžˆλ‹€. 첫째 μ€„μ—μ„œ 숫자λ₯Ό 적절히 λ½‘μœΌλ©΄, κ·Έ λ½‘νžŒ μ •μˆ˜λ“€μ΄ μ΄λ£¨λŠ” μ§‘ν•©κ³Ό, λ½‘νžŒ μ •μˆ˜λ“€μ˜ λ°”λ‘œ λ°‘μ˜ λ‘˜μ§Έ 쀄에 λ“€μ–΄μžˆλŠ” μ •μˆ˜λ“€μ΄ μ΄λ£¨λŠ” 집합이 μΌμΉ˜ν•œλ‹€. μ΄λŸ¬ν•œ 쑰건을 λ§Œμ‘±μ‹œν‚€λ„λ‘ μ •μˆ˜λ“€μ„ λ½‘λ˜, μ΅œλŒ€λ‘œ 많이 λ½‘λŠ” 방법을 μ°ΎλŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€. 예λ₯Ό λ“€μ–΄, N=7인 경우 μ•„λž˜μ™€ 같이 ν‘œκ°€ μ£Όμ–΄μ‘Œλ‹€κ³  ν•˜μž.

이 κ²½μš°μ—λŠ” 첫째 μ€„μ—μ„œ 1, 3, 5λ₯Ό λ½‘λŠ” 것이 닡이닀. 첫째 μ€„μ˜ 1, 3, 5λ°‘μ—λŠ” 각각 3, 1, 5κ°€ 있으며 두 집합은 μΌμΉ˜ν•œλ‹€. μ΄λ•Œ μ§‘ν•©μ˜ ν¬κΈ°λŠ” 3이닀. λ§Œμ•½ 첫째 μ€„μ—μ„œ 1κ³Ό 3을 λ½‘μœΌλ©΄, 이듀 λ°”λ‘œ λ°‘μ—λŠ” μ •μˆ˜ 3κ³Ό 1이 μžˆμœΌλ―€λ‘œ 두 집합이 μΌμΉ˜ν•œλ‹€. κ·ΈλŸ¬λ‚˜, 이 κ²½μš°μ— λ½‘νžŒ μ •μˆ˜μ˜ κ°œμˆ˜λŠ” μ΅œλŒ€κ°€ μ•„λ‹ˆλ―€λ‘œ 닡이 될 수 μ—†λ‹€.

μž…λ ₯

  • 첫째 μ€„μ—λŠ” N(1≀N≀100)을 λ‚˜νƒ€λ‚΄λŠ” μ •μˆ˜ ν•˜λ‚˜κ°€ μ£Όμ–΄μ§„λ‹€. κ·Έ λ‹€μŒ μ€„λΆ€ν„°λŠ” ν‘œμ˜ λ‘˜μ§Έ 쀄에 λ“€μ–΄κ°€λŠ” μ •μˆ˜λ“€μ΄ μˆœμ„œλŒ€λ‘œ ν•œ 쀄에 ν•˜λ‚˜μ”© μž…λ ₯λœλ‹€.

좜λ ₯

  • 첫째 쀄에 λ½‘νžŒ μ •μˆ˜λ“€μ˜ 개수λ₯Ό 좜λ ₯ν•˜κ³ , κ·Έ λ‹€μŒ μ€„λΆ€ν„°λŠ” λ½‘νžŒ μ •μˆ˜λ“€μ„ μž‘μ€ μˆ˜λΆ€ν„° 큰 수의 μˆœμ„œλ‘œ ν•œ 쀄에 ν•˜λ‚˜μ”© 좜λ ₯ν•œλ‹€.

πŸ“ Logic

class Graph { int[] graph; int[] visited; PriorityQueue<Integer> path = new PriorityQueue<>(); }
  • μž…λ ₯λ˜λŠ” μˆ«μžλ“€μ„ μ €μž₯ν•˜λŠ” graph λ°°μ—΄, 각 μ •μ μ˜ λ°©λ¬Έμ—¬λΆ€λ₯Ό μ €μž₯ν•˜λŠ” visited λ°°μ—΄, 사이클을 μ΄λ£¨λŠ” 정점듀을 μ €μž₯ν•˜λŠ” path μš°μ„ μˆœμœ„ 큐
public void solution() { for (int i=1; i<graph.length; i++) { if (dfs(i, i) == 1) { path.add(i); } visited = new int[graph.length]; } printList(); }
  • 각 정점을 μ‹œμž‘μœΌλ‘œ ν•˜μ—¬, dfs 의 λ¦¬ν„΄κ°’μœΌλ‘œ μ‚¬μ΄ν΄μ˜ μ‘΄μž¬μ—¬λΆ€ 확인
  • μ‘΄μž¬ν•˜λŠ” 경우, path μš°μ„ μˆœμœ„ 큐에 μ €μž₯
  • λ°©λ¬Έ μ—¬λΆ€λ₯Ό μ €μž₯ν•˜λŠ” visited μ΄ˆκΈ°ν™”
public int dfs (int start, int end) { if (visited[end] == 0) { visited[end] = 1; return dfs(start, graph[end]); } else { return (start == end) ? 1 : 0; } }
  • μ‹œμž‘μ , μ‹œμž‘μ μ—μ„œ μ΄μ–΄μ§€λŠ” 정점을 인자둜 λ°›μ•„, λ°©λ¬Έμ—¬λΆ€λ₯Ό ν™•μΈν•˜κ³  λ°©λ¬Έ 체크
  • μ΄μ–΄μ§€λŠ” 정점이 λ°©λ¬Έν•œ 경우, μ‹œμž‘μ κ³Ό λ™μΌν•œμ§€ 확인

    • λ™μΌν•œ 경우, 사이클이 쑴재 β†’ 1 λ°˜ν™˜

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Graph { int[] graph; int[] visited; PriorityQueue<Integer> path = new PriorityQueue<>(); public Graph(int size) { graph = new int[size+1]; visited = new int[size+1]; } public void AddElement(int idx, int item) { graph[idx] = item; } public void solution() { for (int i=1; i<graph.length; i++) { if (dfs(i, i) == 1) { path.add(i); } visited = new int[graph.length]; } printList(); } public int dfs (int start, int end) { if (visited[end] == 0) { visited[end] = 1; return dfs(start, graph[end]); } else { return (start == end) ? 1 : 0; } } public void printList() { System.out.println(path.size()); for (int t : path) System.out.println(t); } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); Graph g = new Graph(T); for (int i=1; i<=T; i++) { g.AddElement(i, sc.nextInt()); } g.solution(); sc.close(); } }

✏️ Review

  • 전에 C++둜 ν‘Ό λ¬Έμ œμ˜€λŠ”λ°, JAVA둜 λ³€ν™˜ν•˜λ©΄μ„œ λ‹€μ‹œ ν•œ 번 아이디어λ₯Ό μƒκ°ν•΄λ³΄μ•˜λ‹€.
  • κ·Έλž˜ν”„ 문제이기 λ•Œλ¬Έμ—, 유ν–₯이든 무ν–₯이든 μ–΄μ¨Œλ“  κ·Έλž˜ν”„λ‘œμ˜ ν‘œν˜„μ΄ κ°€λŠ₯ν•˜λ‹€λŠ” 의미라고 생각해 정점 κ°„μ˜ 인접 정보λ₯Ό ν‘œν˜„ν•˜κ³  이λ₯Ό κ·Έλ € 아이디어λ₯Ό μƒκ°ν•΄λ³΄μ•˜λ‹€.
  • 사이클이 μ‘΄μž¬ν•˜λŠ” 경우, 사이클을 ν˜•μ„±ν•˜λŠ” PATHκ°€ 정닡이 λœλ‹€κ³  μƒκ°ν–ˆλ‹€.

    • λ°©λ¬Έν•œ 정점에 λ‹€μ‹œ λ°©λ¬Έν•˜λŠ” 경우둜 κ΅¬ν˜„ν•˜λ €κ³  ν–ˆμœΌλ‚˜, λ°©λ¬Έ μ—¬λΆ€ λ³€κ²½κ³Ό 확인 μ‹œμ μ—μ„œ λ§‰ν˜”λ‹€.

πŸ“• 좜처

https://www.acmicpc.net/problem/2668

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€